sebuah pesawat Air Nauru Fokker F28 Fellowship di Lapangan Terbang Antarabangsa Melbourne, Australia pada Tahun (1973)sebuah pesawat Air Nauru Boeing 737-400 (Beoing 737 Classic) di Lapangan Terbang Antarabangsa Kingsford Smith, Australia pada Tahun (2003)

Nauru Airlines ditubuhkan sebagai Air Nauru pada 17 September 1969[4], dan mula beroperasi pada 14 Februari 1970 dengan perkhidmatan eksperimen antara Nauru dan Brisbane, menggunakan Dassault Falcon 20 (ukuran sederhana jet perniagaan) yang Piagam dari syarikat Australia.[5][6] Perkhidmatan berjadual tetap dimulakan setelah penghantaran pada Januari 1972 jet kembar pertama Fokker F28 Fellowship syarikat penerbangan [5] (Fellowship kedua kemudiannya juga digunakan). Boeing 737-200C telah ditambahkan ke armada pada tahun 1975[7] dan Boeing 727-100 memasuki perkhidmatan pada 16 Jun 1976.[8] Kemudian pada tahun 1970-an dua Fellowship terjual dan lebih banyak Boeings ditambahkan ke armada.

Menjelang 1983 armada itu merangkumi tujuh pesawat: dua Boeing 727-100s dan lima Boeing 737-200;[9] kerana keseluruhan penduduk Nauru pada masa ini sekitar 8,000,[10] syarikat penerbangan tersebut mempunyai kapasiti tempat duduk yang sama dengan 10% daripada populasi Orang Nauru. Syarikat penerbangan itu juga mempunyai reputasi buruk untuk membatalkan penerbangan sesuka hati pemilik kerajaannya, termasuk menggunakan pesawat Boeing 727 untuk pencarian peringkat rendah untuk nelayan Nauru yang hilang di laut sementara saudara-mara di dalam kapal disajikan alkohol oleh pramugari.[11] Dari titik tinggi ini (sekurang-kurangnya dari segi jumlah armada) syarikat penerbangan secara beransur-ansur menguncup, menyewa beberapa pesawat dan menjual yang lain. Lima tahun kemudian pada tahun 1988 armada terdiri dari tiga pesawat Boeing 737-200 dengan satu lagi yang tinggal 727-100 disewakan kepada Trans Australia Airlines. Pada masa ini syarikat penerbangan itu terjejas teruk oleh perselisihan industri dengan juruterbangnya dan beroperasi tanpa jadual waktu yang ditetapkan, situasi yang berlangsung selama beberapa bulan.[12]

Pada awal 1990-an, sebuah Air Nauru 737 disewa untuk mengendalikan laluan Auckland - Niue kepada Syarikat Penerbangan Niue Airlines, satu-satunya perkhidmatan syarikat terakhir.

Pada tahun 1993 dua dari 737-200 digantikan oleh Boeing 737 Classic (Boeing 737-400), meninggalkan Boeing 737-200C untuk tentera untuk sementara waktu lebih lama.[13] Syarikat penerbangan itu, dengan hanya beroperasi satu pesawat 737-400, diperbadankan pada bulan Julai 1996 sebagai Nauru Air Corporation (NAC) yang diketuai oleh CEO baru tanpa hubungan dengan pemerintah, yang membolehkannya beroperasi secara bebas di pasar komersial, bebas dari kebanyakan kekangan kerajaannya.[11]

Sepasang pesawat Syarikat Penerbangan Nauru Airlines Boeing 737-300 (Boeing 737 Classic) di Lapangan Terbang Antarabangsa Nauru (Februari 2016)

Pada tahun 1998 Air Nauru berada di bawah kawalan pengawalseliaan Pihak Berkuasa Penerbangan Awam Australia dan sejak itu telah menjadi syarikat penerbangan asing terpilih yang memegang Sijil Pengendali Udara Australia (AOC). Salah urus kekayaan pulau itu dan masalah ekonomi yang dihasilkan menyebabkan syarikat penerbangan kehilangan sejumlah besar wang, dan dalam beberapa kesempatan menjadi muflis (Bankrupt). Operasinya juga ditangguhkan untuk jangka masa pendek pada tahun 1990-an kerana kebimbangan yang dikemukakan oleh Australia mengenai rekod kelayakan dan keselamatan pesawatnya. Pejabat dan peralatan syarikat penerbangan juga sering diambil alih oleh pemerintah Australia kerana kelalaian pinjaman asing oleh Nauru. Syarikat penerbangan tersebut menjadi pertikaian dengan Export-Import Bank of the United States pada tahun 2002, dan pada bulan Disember 2005 Mahkamah Tinggi Australia menegaskan keputusan sebelumnya untuk membenarkan bank untuk merampas satu-satunya pesawat Air Nauru, meninggalkan Nauru[14] dan Negara Kepulauan Kiribati[petikan diperlukan] tanpa perkhidmatan penerbangan. Pesawat tersebut mencari dan menyita (disita) oleh pemiutang di Lapangan Terbang Antarabangsa Melbourne pada 18 Disember 2005.[15][pautan mati] Berikutan pemerolehan pesawat pengganti (Boeing 737-300) pada pertengahan tahun 2006, syarikat penerbangan ini dijenamakan semula sebagai Syarikat Penerbangan Our Airline dan dilancarkan semula pada 14 Oktober 2006. [16] Syarikat Penerbangan Our Airline dinamakan semula menjadi Nauru Airlines pada 1 Ogos 2014.

Nauru Airlines kini dimiliki sepenuhnya oleh negeri dan mempunyai 65 pekerja pada bulan Julai 2012.[17]